#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <unistd.h>
#include <stdatomic.h>
#include <threads.h>
#include <stdbool.h>
#include "cas.h"
typedef struct {
    _Atomic(QueueNode*) head;
    _Atomic(QueueNode*) tail;
} QPOS; // next字段指向节点
QPOS Q = {0};
#define CAS(obj, expect, des) \
    atomic_compare_exchange_weak((obj), (expect), (des))
// QueueNode *head;
// QueueNode *tail;
int QueueInit()
{
    //头节点
    Q.head       = (QueueNode*)calloc(1, sizeof(QueueNode));
    Q.head->next = NULL;
    Q.tail       = Q.head;
    return 0;
}

//先加入节点，后改变tail
void QueuePush(QueueNode* node)
{
    QueueNode* old_tail = NULL;
    QueueNode* next     = NULL;
    while(1) {
        old_tail = atomic_load(&Q.tail);
        next     = atomic_load(&Q.tail->next);
        //多线程中，会出现tail改变和next改变
        //如果tail改变
        if(old_tail != Q.tail) { continue; }

        //如果next改变
        if(next != NULL) {
            //尝试更新tail到next
            CAS(&Q.tail, &old_tail, next);
            continue;
        }

        //满足上述条件，尝试让节点入队，直到成功(此时的next需要为NULL)
        // if(CAS(&(Q.tail->next),NULL,node)){ //与下一行作用一样
        if(CAS(&(Q.tail->next), next, node)) { break; }
    }
    // atomic_compare_exchange_strong/weak
    //尝试更新tail
    // old_tail指向的节点一定在node前
    CAS(&Q.tail, &old_tail, node);
}
int QueuePop(QueueNode* node)
{
    QueueNode* old_head;
    QueueNode* old_tail;
    QueueNode* old_next;
    while(1) {
        old_tail = atomic_load(&Q.tail);
        old_head = atomic_load(&Q.head);
        old_next = atomic_load(&(Q.head->next));

        /*
        //如果head已经移动
        if(old_head!=atomic_load(&Q.head)){
            continue;
        }

        //如果为空队列
        if(old_tail == old_head&&old_next == NULL){
            return -1;
        }

        //如果old_head赶上old_tail(上一步已经确定了不为空)(如果next为null，表示取出old_head时,)
        if(old_tail == old_head&&old_next == NULL){

        }*/
        if(old_head == Q.head) {
            if(old_head->next == old_tail->next) {
                if(old_next->next == NULL) {
                    return -1;
                } else {
                    CAS(&Q.tail, &old_tail, old_next);
                }
            } else {
                if(CAS(&Q.head, &old_head, old_next->next)) {
                    node->i = old_next->i;
                    break;
                }
            }
        }
    }
    free(old_head->next);
    return 0;
}

//参考博客：https://coolshell.cn/articles/8239.html
//参考论文：https://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf